package 算法.排序;

import java.util.HashSet;

public class JZ3数组中重复的数字 {

    //位置重排
    //在一个长度为n的数组里的所有数字都在0到n-1的范围内。
    //[2,3,1,0,2,5,3]  2/3
    public int duplicate2(int[] numbers) {
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] == i)
                continue;
            else {
                if (numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                else {
                    swap(numbers, i, numbers[i]);
                    i--;
                }
            }
        }
        return -1;
    }

    void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public int duplicate(int[] numbers) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        for (int num : numbers) {
            if (set.contains(num))
                return num;
            set.add(num);
        }
        return -1;
    }
}